\chapter{Structural Authentication Scheme}
In this chapter \cite{kundustructural} the structural authentication scheme will be developed. Structural signatures are based on post-order and pre-order numbers for non-binary trees, and those of binary trees are defined by in-order traversals and either the post-order or pre-order traversals.
\newline

\section{Structural Position}
The structural position of a node uniquely identifies a node in the tree using RRON and RPON for non-binary trees and using RION and RRON/RPON for binary trees. The integrity verifier IV of a node is computed for each node using its structural position and its content. The verification object $\mathcal{VO}$ is computed from the IVs and is used to verify the authenticity of the subtree.
\newline
\textit{Definition (structural position and integrity verifier)}: The structural position of a node $\mathit{x}$ in a tree T(V,E), denoted by $\theta_x$ is a pair of its RPON p$_x$ and RRON r$_x$ (RION i$_x$ and either of RRON r$_x$ or RPON p$_x$ in case of binary trees), that is $\theta_x$ = (p$_x$ , r$_x$). Let c$_x$ denote the content of node $\mathit{x}$, then its structural integrity verifier (IV), denoted by $\xi_x$ is defined as $\xi_x$ = $\mathcal{H}$($\theta_x$ $\parallel$ c$_x$).
\newline

The leakage free structural signature $\psi$T(V,E) of T(V,E) is computed using the IVs of each node. We can salt the signature of the tree with a random value when the shared subtree is the same as the whole tree. The (salted) tree signature is publicly available or is given to the user while sending the shared subtree. $\psi$T(V,E) is an aggregate signature, computed over the IVs of its nodes. We define two types of aggregate signatures for trees: one based on the condensed-RSA signatures $\cite{mykletun2006authentication}$ and the other based on bilinear maps $\cite{boneh2003aggregate}$ which are explained as below:
\newline
\section{Structural Signature using Condensed RSA}
In this section we will define structural signatures using condensed RSA, but a brief review of the standard RSA scheme followed by condensed RSA.
\newline

\textit{Review of Standard RSA : }
RSA is an asymmetric key based encryption technique where a pair of public-private keys are generated. The public key is published publicly. Now a message m is encrypted using the public key and only the user having the private key can read the contents of the message.
\newline
Lets say we have a message converted to a number m. The number m is raised to a public exponent e and a modulus of the result by a random number N. The output of this method is the cipher c, that is c = m$^e$ mod N
\newline
Thus given the public key e and the random number N (also public), it is difficult to figure out the message m from the cipher c. Only the person having the private key d can get back m. To do this we need a special relationship between e and d, which can be achieved by using the following mathematical relations: 
\newline
a) RSA is based on the fact that prime factorization is a hard problem. This fact is exploited and we get the one-way function we need. We take two prime numbers (each of 250 bits long) p and q, then finding the product N=p.q is easy, but given N finding the prime factors p and q is a hard problem (the prime factorization of N is our one-way function).
\newline
b) The totient function or phi function of a number p (denoted by $\phi$(p))is defined as the number of numbers from 1 to (p-1) which do not share a common factor with p. According to this $\phi$(p) = p-1 when p is a prime number. Also, a property of this phi function is that $\phi$(a.b) = $\phi$(a).$\phi$(b). In our case N = p.q, so $\phi$(N) = $\phi$(p.q) = $\phi$(p).$\phi$(q) = (p-1).(q-1). 
\newline
c) Euler's Theorem: According to Euler's theorem if 'a' and N are co-prime positive integers then a$^{\phi(N)} \equiv $1(mod N). This leads to a$^{k.\phi(N)+1}$ $\equiv$ a mod N.
\newline

These relations give rise to the standard RSA algorithm where the relationship between e and d is such that e.d = k.$\phi(N) + 1$. (N is a 500 bit long number and is public, e is a randomly chosen public key, k needs to be chosen such that d is an integer) .The computation of d can only be done if one knows $\phi(N)$ (knowing $\phi(N)$ means knowledge of p and q, computing p and q from N is hard as said before). So finally we have the following: 
\newline
(msg)$^{e.d}$ $\equiv$ (msg) mod N.
\newline
The beauty of this relationship between is e and d is such that if a person sends a cipher (c = msg$^{e}$ mod N), then it can be only decrypted by a person having the secret key d as follows: \newline
c$^{d}$ mod N = msg$^{e.d}$ mod N $\equiv$ msg mod N
\newline
We can also have the sender generating and sending the RSA signature of the message as $\psi(msg)$ = msg$^{d}$ mod N, and the receiver verifying the message by checking $\psi(msg)^{e}$ $\stackrel{?}{\equiv}$ msg mod N.
\newline

\textit{Review of Condensed RSA}: 
We have the standard RSA parameters like secret key d, public key e,N and we hash our messages using a cryptographic hash function $\mathcal{H}$. Lets say we have m messages M$_1$, M$_2$, .... M$_m$. The condensed signature of these messages is computed by first computing the $\psi_i$ for each message M$_i$ (1$\leq$i$\leq$m) and then computing the product of all these $\psi_i$. Thus we have $\psi_{1,m}$ = Condensed Signature = $\prod_{i=1}^m$ $\psi_{i}$ mod N. The size of the condensed signature is the same as that of each individual signature. Hence the bandwidth load on transferring the condensed signature is the same as that of transferring a single signature.
\newline
Condensed Singature Verification: If none of the messages M$_i$ or signatures $\psi_i$ have been tampered then the following equality must holds true: 
$(\psi_{1,m})^e$ $\stackrel{?}{\equiv}$ $\prod_{i=1}^{m}\mathcal{H}(M_i)$ mod N

\textit{Choosing Condensed RSA over Batch RSA}: 
In batch RSA the receiver is given all individual signatures $\psi_i$, and all the individual messages M$_i$, and the receiver verifies if the above equation holds true. The main difference between condensed RSA and batch RSA is that in the latter all the products of signatures is computed at the receiver's side. This increases the number of multiplications and exponential calculations that has to be performed at the receiver's side. Thus, condensed RSA saves (m-1).$\abs{N}$ bits of bandwidth and saves (m-1) multiplications. Also, $\cite{mykletun2006authentication}$ CRSA is at-least as secure as batch RSA assuming RSA is a one way function. Thus we choose condensed RSA over batch RSA.

\textit{Definition Structural Signatures using Condensed RSA}: Let T(V,E) be a tree. Let $\mathcal{H}$ denote a cryptographic hash function. Let the RSA signature $\psi_x$ of each node $\mathit{x}$ be defined as follows $\psi_x$ $\leftarrow$ $\xi_x^d$ mod n, where $\xi_x$ is the IV of node x. Let $\omega_T$ be a random. The leakage-free signature of T, denoted by $\psi_{T(V,E)}$, is defined as $\psi_{T(V,E)}$ = ($\omega_T$.$\displaystyle\prod_{x \in V} \xi_x$)$^d$ (mod n).  \cite{kundustructural} (1).
\newline

\section{Structural Signatures using Aggregate Signatures}

Boneh-Gentry-Lynn-Shacham signature scheme $\cite{boneh2003aggregate}$ known as BGLS scheme consist of some steps:
\begin{enumerate}
	\item Suppose G$_{1}$ and G$_{2}$ be two Group of prime order P.
	\item g$_{1}$ and g$_{2}$ being the generator of elements for the groups G$_{1}$ and G$_{2}$ respectively.
	\item $\mathit{e}$ is the Bilinear Map $\mathit{e}$ : G$_{1}$ $\times$ G$_{2}$  $\rightarrow$ G$_{T}$, where G$_{T}$ is another Multiplicative Group.
\newline

Bilinear Map function $\mathit{e}$ posses two major properties:
\begin{enumerate}
	\item $\mathit{e}$ is Bilinear which means if 'a' $\in$ G$_{1}$ , 'b' $\in$ G$_{2}$ and 'x', 'y' $\in$  $\mathbb{Z}$ then:
	\newline
	$\mathit{e}$(a$^{x}$,b$^{y}$) = $\mathit{e}$(a,b)$^{xy}$
	\item $\mathit{e}$ is Non-Generative which means that:
	\newline
	$\mathit{e}$(g$_{1}$,g$_{2}$) $\neq$ 1
\end{enumerate}
	\item A Hash Function $\mathit{H}$ : $\lbrace$0,1$\rbrace$$^{*}$  $\rightarrow$ G$_{1}$ viewed as a random oracle.
\end{enumerate}
The main concept of the scheme is to check the authenticity of a message 'M' using signatures.The signature is computed on the bases of a secret key 'x'.
The message is hashed and then this based is raised to the power of secret key as $\mathit{h}$$^{x}$. This is the signature of the message 'M'. Now this message is broadcasted with hash and signature and is verified by using the verification scheme.
\newline

Three algorithms are used for the signature scheme which are as follows:
\begin{enumerate}
	\item Key Generation: Sender chooses a secret key 'x' from the set  $\mathbb{Z}$$^{p}$ and generates the public key 'v' as v = g$_{2}$$^{x}$
	\item Signing: For a message M the hash is calculated and then the signature is generated as $\sigma$ = $\mathit{h}$$_{x}$ which is hash of the message $\mathit{h}$ raised to the power of secret key 'x'.
	\item Verification: Given The public key 'v', signature $\sigma$, he computes the hash 'h' of the message 'M', the message is verified if (g$_{2}$, v, h,$\sigma$) is a co-CDHP tuple i.e. e($\sigma$,g$_2$) = e(h,v).
\end{enumerate}
 
\textit{Aggregate Signatures}:
In our discussion we will take 'P' as our group generator for Group  G$_{2}$ i.e, G$_{2}$ = $<$$\mathit{e}$(P,P)$>$, thus if we know 'P' we can generate  G$_{2}$.  G$_{2}$ is a multiplicative group of prime order 'p'.  G$_{1}$ is an additive group of prime order 'p'. We have the mapping $\mathit{e}$ : G$_{1}$ $\times$ G$_{2}$  $\rightarrow$ G$_{2}$, where $\mathit{e}$ is the bilinear map function. There fore  $\mathit{e}$(aX, bY) =  $\mathit{e}$(a,b)$^{XY}$ where a,b $\in$ $\mathbb{Z}$$^{*}$$_{P}$.
\newline

In this arrangement if P, aP and X are given but not 'a', then aX cannot be computed because co-CDHP is hard. 
\newline

Q = sk*P where 'Q' is the Public Key and 'sk' is the randomly chosen secret key where sk $\in$ $\mathbb{Z}$$^{*}$$_{P}$ and Q $\in$ G$_{2}$. Signature for message 'm' is sk*M where
\newline
M = $\mathit{H}$(m) such that each M $\in$ G$_{1}$ for each message 'm'
\newline
Being Given P, Q and k message signature pairs skM$_{i}$ where 1$\le$i$\le$k. Aggregate signature can be verified by proving the equality:
$\mathit{e}$(Q,$\displaystyle\sum_{i = 1}^{k}$ M$_{i}$) = $\mathit{e}$(P,$\displaystyle\sum_{i = 1}^{k}$ $\psi_i$)

\textit{Proof of $\mathit{e}$(Q,$\displaystyle\sum_{i = 1}^{k}$ M$_{i}$) = $\mathit{e}$(P,$\displaystyle\sum_{i = 1}^{k}$ $\psi_i$)}:
\newline
$\Longrightarrow$$\mathit{e}$(Q,$\displaystyle\sum_{i = 1}^{k}$ M$_{i}$) [Starting from Left Hand Side]
\newline
$\Longrightarrow$$\mathit{e}$(sk*P,$\displaystyle\sum_{i = 1}^{k}$ M$_{i}$) [Putting Q = sk*P]
\newline
$\Longrightarrow$$\mathit{e}$(P,$\displaystyle\sum_{i = 1}^{k}$ M$_{i}$)$^{sk}$ [Using Bilinear maps property e(aX,Y) = e(X,Y)$^a$]
\newline
$\Longrightarrow$$\mathit{e}$(P,sk*$\displaystyle\sum_{i = 1}^{k}$ M$_{i}$) [Using Bilinear maps property e(X,Y)$^a$ = e(X,aY)]
\newline
$\Longrightarrow$$\mathit{e}$(P,$\displaystyle\sum_{i = 1}^{k}$ {M$_{i}$*sk}) [Simplifying]
\newline
$\Longrightarrow$$\mathit{e}$(P,$\displaystyle\sum_{i = 1}^{k}$ $\psi_i$)
\newline
This is Right Hand Side. Hence Proved.
\newline

\textit{Aggregate Structural Signatures}: Let T(V,E) be the tree and $\mathit{H}$ belong to the random oracle. Let the signature $\psi_x$ denote the signature of node x, define as $\psi_x$$\leftarrow$sk$\xi_x$, where $\xi_x$ is the $\mathit{IV}$ of $\mathit{x}$. Let $\omega_T$ be a random salt then the aggregated signature will be defined as:
$\psi_{T(V,E)}$ $\leftarrow$ $\mathit{e}$(P,sk($\omega_T$+$\displaystyle\sum_{x \in V}$ $\xi_x$)). (2) $\cite{kundustructural}$


\section{Signing a Tree}
The algorithm performed by the trusted owner to calculate the IVs for a tree T(V,E) is a follows: 
\newline

\textit{Algorithm}: 
\begin{enumerate}
	\item Compute the pre-order and post-order numbers of each node in the tree.
	\item For each node x in the tree transform the pre-order and post-order numbers into randomized pre-order and randomized post-order numbers, denoted by r$_x$,p$_x$ respectively such that: 
		\subitem For unordered trees the transformation need not preserve the order of the siblings, but must preserve order between parent and child nodes.
		\subitem For ordered trees the transformation must preserve all the ordering of the nodes.
	\item For each node $\mathit{x}$,
		\subitem Compute the structural position of a node $\mathit{x}$ as $\theta_x$ = (p$_x$,r$_x$).
		\subitem Compute the IV of node $\mathit{x}$ $\xi_x$ $\leftarrow$ $\mathcal{H}(\theta_x \parallel c_x)$
	\item The leakage free signature $\psi_{T(V,E)}$ will be obtained either from Condensed RSA (Eqn. 1) or from the BGLS (Eqn. 2). 
\end{enumerate}

\textit{How to Compute Randomized traversal numbers}: 
The simplest scheme is to pick $\mathsf{n}$ random numbers and sort them where $\mathsf{n}$ is the number of nodes in the tree. Then assign these sorted numbers as the randomized pre-order traversal numbers in the order of pre-order numbers. We can repeat the same process for post-order numbers and get randomized post-order numbers. Thus we get the sequence of (p$_x$,r$_x$) for all x $\in$ V.
\newline
Another method to get random traversal numbers which focuses on keeping the interval between two adjacent random traversal numbers in a random. In this method a single random number $\eta$ is chosen as the interval distance or $\eta$ can be computed as follows: pick a random number say m, then pick m number of random numbers and compute $\eta$=sum of all these m random numbers.
\section{Distribution of a Subtree}
The end user $\mathcal{B}$ can receive a shared subtree $T_{\delta}(V_{\delta},E_{\delta})$ of the tree T(V,E) in two ways: 1) sharing the signed subtree , its node and its structure. 2) by sharing the signed nodes in the subtree and letting $\mathcal{B}$ reconstruct the subtree using the RPON’s and RRON’s of the nodes. In both the security algorithms viz Condensed RSA and BGLS the distributor D only needs to send O(1) (not depending on the size of the subtree requested) authenticity verifiers to the user.
\section{Sharing Subtree along with its Structure}
The distributor D sends the following items to $\mathcal{B}$, who has access to the subtree $T_{\delta}(V_{\delta},E_{\delta})$: 
\begin{enumerate}
	\item Signature $\psi_{T(V,E)}$.
	\item Each node x $\in$ $V_{\delta}$, its structural position $\theta_x$ and IV$_x$.
	\item Aggregate signature of the nodes, that is $\psi_{T_{\delta}}$ computed as follows: \\
	in CRSA $\psi_{T_{\delta}}$ = $\displaystyle\prod_{x \in V} \psi_x$ mod n; \\
	in BGLS $\psi_{T_{\delta}}$ = e(P,$\displaystyle\sum_{x \in V} \psi_x$).\\
	\item \textit{While proving these equations we found was a printing mistake in \cite{kundustructural}($\psi_x$ was present instead of $\xi_x$, we corrected it) in the value of the Verification Object VO, thus we are using the corrected values of VO}. \\
	If CRSA then VO $\leftarrow$ $\omega_T$.$\displaystyle\prod_{x \in V-V_{\delta}} \xi_x$ mod n;\\
	If BGLS then VO $\leftarrow$ $\omega_T$ + $\displaystyle\sum_{x \in V-V_{\delta}} \xi_x$
	\item As we are sharing the subtree along with its structure we give information about structural ordering between the nodes and parent-child relationships in the form of adjacency matrix.
\end{enumerate}

\section{Authentication}
The authentication section includes authentication of contents. If the contents are not verified then precise validation finds out exactly which node has been tampered. Then we also verify the structural relations.
\newline
\subsection{Authentication of Contents}
$\mathcal{B}$ receives the subtree T$_{\delta}^{\prime}$(V$_{\delta}^{\prime}$,E$_{\delta}^{\prime}$) (to avoid naming ambiguity), the structural position $\theta_x$ of each node $\mathit{x}$, VO and the signature of the tree $\psi_{T(V,E)}$.
\textit{Authentication of Contents}
The Authentication of the Contents in CRSA
\begin{enumerate}
	\item Let k = $\abs{V_{\delta}^{\prime}}$.
	\item For each node y  in the set of received nodes $V_{\delta}^{\prime}$ compute $\xi_y$ = $\mathcal{H}(\theta_y \parallel c_y)$.
	\item $\displaystyle\prod_{y \in V_{\delta}^{\prime}} \xi_{y} \stackrel{?}{=}$ ($\psi_{T_{\delta}^{\prime}}$)$^e$ mod n.
	\item VO. $\displaystyle\prod_{y \in V_{\delta}^{\prime}}$ $\xi_y$ $\stackrel{?}{=}$ ($\psi_T$)$^e$ mod n.
	\item If (3) and (4) are true, the contents and structural positions of T$_{\delta}^{\prime}$(V$_{\delta}^{\prime}$,E$_{\delta}^{\prime}$) are authenticated.
	\item If (4) is true and (3) is false, at least one of the nodes in $V_{\delta}^{\prime}$ is an unauthorized node.
	\item If (3) is true and (4) is false, at least one of the nodes in T(V,E) has been dropped from either $V_{\delta}^{\prime}$ or VO.
\end{enumerate}

For BGLS Signatures: Replace Steps (3) and (4) by the following ones, respectively.
\begin{description}[font=\normalfont\itshape\textbullet\space]
	\item[(Step 3):] e(Q , $\displaystyle\sum_{y \in V_{\delta}^{\prime}}$ $\xi_y$) $\stackrel{?}{=}$ $\psi_{T_{\delta}^{\prime}}$.
	\item[(Step 4):] e(Q , VO + $\displaystyle\sum_{y \in V_{\delta}^{\prime}}$ $\xi_y$ $\stackrel{?}{=}$ $\psi_T$.
\end{description}

If no data has been tampered then equations (3) and (4) must hold true for both RSA and BGLS.\\
Thus proving equations (3) and (4) using RSA:\\
\\
(3) $\Longrightarrow$ $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_{y} \stackrel{?}{=}$ ($\psi_{T_{\delta}^{\prime}}$)$^e$ mod n\\
$\hspace*{6 mm}\Longrightarrow$ $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_{y} \stackrel{?}{=}$ \big($\displaystyle\prod_{y \in T_{\delta}^{\prime}}\psi_y$ mod n\big)$^e$ mod n [Simplifying RHS using def of $\psi_{T_{\delta}^{\prime}}$]\\
$\hspace*{6 mm}\Longrightarrow$ $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_{y} \stackrel{?}{=}$ \Bigg($\displaystyle\prod_{y \in T_{\delta}^{\prime}}\psi_{y}^{e}$ mod n\Bigg) mod n [Simplifying RHS using (a.b)$^e$ = a$^e$.b$^e$]\\
$\hspace*{6 mm}\Longrightarrow$ $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_{y} \equiv$ $\displaystyle\prod_{y \in T_{\delta}^{\prime}}\xi_y$ mod n [Simplifying RHS using property of RSA]\\
\\
Hence Proved.\\
\\
(4) $\Longrightarrow$ VO. $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_y$ $\stackrel{?}{=}$ ($\psi_T$)$^e$ mod n\\
$\hspace*{6 mm}\Longrightarrow$ VO. $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_y$ $\stackrel{?}{=}$ \Big(\big($\omega_T.\displaystyle\prod_{y \in V}\xi_{y}$\big)$^d$\Big)$^e$ mod n [Simplifying RHS using def of $\psi_T$]\\
$\hspace*{6 mm}\Longrightarrow$ VO. $\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_y$ $\stackrel{?}{=}$ $\omega_T.\displaystyle\prod_{y \in V} \xi_y$ mod n[Simplifying RHS using RSA property]\\
$\hspace*{6 mm}\Longrightarrow$ ($\omega_T.\displaystyle\prod_{y \in V-V_{\delta}^{\prime}}\xi_y$).($\displaystyle\prod_{y \in V_{\delta}^{\prime}}\xi_y$) $\stackrel{?}{=}$ $\omega_T.\displaystyle\prod_{y \in V}\xi_y$ mod n[Putting value of VO on LHS]\\
$\hspace*{6 mm}\Longrightarrow$ $\omega_T.\displaystyle\prod_{y \in V}\xi_y$ $\equiv$ $\omega_T.\displaystyle\prod_{y \in V}\xi_y$ mod n [Simplifying LHS]\\
\\
Hence Proved.\\
Proving Eqns (3) and (4) using BGLS:\\
\\
(3) $\Longrightarrow$e(Q , $\displaystyle\sum_{y \in V_{\delta}^{\prime}}\xi_y$) $\stackrel{?}{=}$ $\psi_{T_{\delta}^{\prime}}$\\
$\hspace*{6 mm}\Longrightarrow$e(skP , $\displaystyle\sum_{y \in V_{\delta}^{\prime}}\xi_y$) $\stackrel{?}{=}$ e(P , sk$\displaystyle\sum_{y \in V_{\delta}^{\prime}}\psi_y$) [Simplifying L.H.S by putting Q = skP]\\
$\hspace*{6 mm}\Longrightarrow$e(P , $\displaystyle\sum_{y \in V_{\delta}^{\prime}}\xi_y$)$^{sk}$ $\stackrel{?}{=}$ e(P , sk$\displaystyle\sum_{y \in V_{\delta}^{\prime}}\psi_y$) [using bilinear Map Property on LHS]\\
$\hspace*{6 mm}\Longrightarrow$e(P , sk$\displaystyle\sum_{y \in V_{\delta}^{\prime}}\xi_y$) $\stackrel{?}{=}$ e(P , sk$\displaystyle\sum_{y \in V_{\delta}^{\prime}}\psi_y$) [using bilinear Map Property on LHS]\\
$\hspace*{6 mm}\Longrightarrow$e(P , sk$\displaystyle\sum_{y \in V_{\delta}^{\prime}}\psi_y$) = e(P , sk$\displaystyle\sum_{y \in V_{\delta}^{\prime}}\psi_y$) [By simplifying L.H.S we get]\\
$\hspace*{6 mm}$Hence proved\\
\\
(4) $\Longrightarrow$e(Q , VO + $\displaystyle\sum_{y \in V_{\delta}^{\prime}}\xi_y$ )$\stackrel{?}{=}$ $\psi_T$\\
$\hspace*{6 mm}\Longrightarrow$ e(Q , $\omega_T$+$\displaystyle\sum_{y \in V-V_{\delta}^{\prime}}\xi_y$ + $\displaystyle\sum_{y \in V_{\delta}^{\prime}}\xi_y$) $\stackrel{?}{=}$ $\psi_T$ [Simplifying LHS, expanding VO]\\
$\hspace*{6 mm}\Longrightarrow$ e(Q,$\omega_T$ + $\displaystyle\sum_{y \in V}\xi_y$) $\stackrel{?}{=}$ $\psi_T$ [simplifying L.H.S]\\
$\hspace*{6 mm}\Longrightarrow$ e(Q,$\omega_T$ + $\displaystyle\sum_{y \in V}\xi_y$) $\stackrel{?}{=}$ e(P,sk($\omega_T$+$\displaystyle\sum_{y \in V}\xi_y$))[simplifying R.H.S using def of $\psi_T$]\\
$\hspace*{6 mm}\Longrightarrow$ e(sk.P,$\omega_T$ + $\displaystyle\sum_{y \in V}\xi_y$) $\stackrel{?}{=}$ e(P,sk($\omega_T$+$\displaystyle\sum_{y \in V}\xi_y$))[simplifying L.H.S using Q=sk.P]\\
$\hspace*{6 mm}\Longrightarrow$ e(P,sk($\omega_T$ + $\displaystyle\sum_{y \in V}\xi_y$)) = e(P,sk($\omega_T$+$\displaystyle\sum_{y \in V}$ $\xi_y$))[simplifying L.H.S using Bilinear Maps Property]\\
$\hspace*{6 mm}$Hence proved\\
\subsection{Precise Verification}
An advantage of structural authentication scheme is that if some nodes in the shared subtree T$_{\delta}^{\prime}$ are invalid, they can precisely be identified. This can be achieved as follows for any node $\mathit{x}$, and is repeated for each node in T$_{\delta}^{\prime}$. Assign k
to 1, and repeat the steps (4) and (5) for CRSA, and (4), (5), and (6) for BGLS (for steps see section 7.7.1).\\

\subsection{Verification of Structural Relations}
Structural Relations can be verified by comparing the RRON/RPON of each node with its parent or siblings. To verify just find the pre-order or post-order traversal of the shared subtree. For two nodes, one being the parent of another in the shared subtree, if the randomized post-order traversal number $\mathit{p}_{x}$ of child is greater than that of the parent then the structural relation is incorrect. Similarly, if randomized pre-order number $\mathit{r}_{x}$ of a parent is greater than that of its child , it shows an ambiguity. \\
In case of left and right siblings, the left-right sibling order is correct only if both $\mathit{p}_{x}$ and $\mathit{p}_{x}$ of the right sibling is greater than those of its left sibling. 

\section{Sharing a Subtree - only the nodes}
Structural Signature Scheme is more efficient as less amount of data is required to be transmitted with the subtree. Distributor sends the signature $\psi_{T(V,E)}$, Each node x $\in$ $V_{\delta}$, its structural position $\theta_x$ and IV$_x$, aggregate signature of the nodes, that is $\psi_{T_{\delta}}$ computed as follows: in CRSA $\psi_{T_{\delta}}$ = $\displaystyle\prod_{x \in V} \psi_x$ mod n; in BGLS \\$\psi_{T_{\delta}}$ = $\mathit{e}$(P,$\displaystyle\sum_{x \in V} \psi_x$). It is not required to supply the structure of the shared subtree. The structure can be reconstructed by using the pre-order and post-order in case of non-Binary \cite{das1994efficient} and in-order and pre/post-order traversal in a Binary tree \cite{kamakoti1992optimal}.
\subsection{Authentication and Reconstruction of a Subtree}
RPON and RRON are the structural positions of this structural authentication scheme. They are similar to pre-order and post-order traversal number because their order is maintained while being randomized. The subtree reconstruction algorithm \cite{das1994efficient} can thus use RPONs and RRONs. The structural integrity is being catered in the reconstruction of the tree.  For binary trees, the algorithm given in \cite{kamakoti1992optimal} can be used, where RIONs would be used. A subtree is itself a tree (since a tree is a recursive data structure), which is why using the algorithm, a subtree can be uniquely reconstructed from the knowledge of the nodes of the subtree, and their respective structural positions.
\newline

We attempted to generate a simple tree using pre and post-order traversal number and we reached the following results on the basis of which a number of combinations can occur which can lead to a single tree:
\begin{enumerate}
	\item The First Node of every pre-order and last node of post-orders represent the root of the tree.
	\item If there are 'k' nodes in both traversal than the 2$^{nd}$ node of pre-order represent the first left child of the root and the $(k-1)^{th}$ node of post-order represent the right child of the root node and so on.
	\item If two consecutive nodes u and v in the post-order appear reversed in the pre-order, then u is the rightmost child of v. 
\end{enumerate}
\section{Illustration}
\begin{figure}[!h]
	\centering
	\includegraphics[scale=0.7]{Images/Travel_Record_with_PON_RON.png}
	\caption{Post-order and pre-order number assigned to the TravelRecord as (PON,RON).}
	%\label{}
	%\cite{}
\end{figure}
\begin{figure}[!h]
	\centering
	\includegraphics[scale=0.7]{Images/Travel_Record_with_randomized_RPON_RRON.png}
	\caption{Randomized post-order and pre-order number assigned to the TravelRecord as (RPON,RRON).}
	%\label{}
	%\cite{}
\end{figure}

In this section we will give an illustration how the proposed scheme prevents leakages (that occurred in MHT) and verifies the structural relationship. Lets take the $\mathit{TravelRecord}$ example (in Chapter 5), in figure 7.1, the tree has been assigned post-order and pre-order traversal numbers (PON,RON present near each node) and in figure 7.2 we have their corresponding randomized versions (RPON,RRON present near each node).Each node has a content which has a value of the name of its element and we also have the IV$_x$ of each node $\mathit{x}$ which is equal to $\xi_x$ = $\mathcal{H}$($\theta_x \parallel c_x$), this hash is not displayed (later versions of such hash functions like SHA3 is 512 bits long) here, but stored in the database server of the distributor. The XML document is signed by the proposed leakage free authentication scheme. The document tree T(V,E), its signature $\psi_{T(V,E)}$, the structural position of each node $\theta_x$, and the salt $\omega_T$ (only required in cases where we want to hide the fact that a shared subtree is actually the whole tree) are stored at the database server of the distributor.
\newline
 
In scenario one, a promotional offer is send to the customers via email, thus the subtree T$_{\delta 1}$ needs to be shared. The database server sends the nodes D$_{2:1}$, D$_{3:1}$, D$_{4:0}$ and D$_{5:0}$, their structural positions, the salted tree signature $\psi_T$ and VO. VO is computed by D by using all the nodes y such that y $\in V - V_{\delta}$. The promoter applies the authentication procedure (authentication of contents followed by verification of structural relationships if the previous is successful). He computes the IV of each node he receives using the relation IV$_x$ = $\xi_x$ = $\mathcal{H}$($\theta_x$ $\parallel$ c$_x$) (here it will be hash of (54,135) and the content of node D$_{2:1}$, similarly for other received nodes). If this authentication is successful then the verification of structural orderings can be carried out. The structural ordering of nodes D$_{2:1}$ and D$_{3:1}$ can be done as follows: in the received subtree D$_{3:1}$ is the parent of D$_{2:1}$, thus p$_{D_{3:1}}$ should be greater than p$_{D_{3:1}}$ (91 $>$ 54 is true), so by post-order number checking we find that node D$_{3:1}$ can be either a parent or left sibling of node D$_{2:1}$. Thus we confirm the relationship using pre-order checking. The pre-order number r$_{D_{2:1}}$(=135) is greater than r$_{D_{3:1}}$(=76), so the node D$_{3:1}$ cannot be a left sibling of node D$_{3:1}$. Thus we can confirm that D$_{3:1}$ is a parent of D$_{2:1}$.
\newline

In second scenario, the user has access to the received subtree T$_{\delta2}$, but it is tampered. If the contents of the subtree is tampered then the user who will be following the authentication procedure (in Section 7.7.1) will know that the contents has been tampered (either equation 3 or 4 will fail) and then the user can find exactly which node(s) has been tampered with by following the procedure(in Section 7.7.2). However if the structural relations has been tampered (say node D$_{2:4}$ is given as the right sibling of D$_{3:5}$). Such a violation in structural relationships can be detected (using the method in Section 7.7.3) as follows: the user has the RPON,RRON pair of all its nodes. Since the node D$_{2:4}$ is given as the right sibling of D$_{3:5}$, so by following the properties of traversal numbers we should have RRON and RPON of node D$_{3:5}$ lesser than the RRON and RPON of node D$_{2:4}$. On verification we have p$_{D_{3:5}}$(=535) greater than p$_{D_{2:4}}$(=478), so node D$_{2:4}$  cannot be the right sibling of node D$_{3:5}$). Thus structural relationships has been violated.